#include <iostream>
using namespace std;

const int MAX = 1000;

void merge(int arr[], int p, int q, int r) 
{
	int m = q - p;
	int n = r - q;
	int* left = new int[m];
	int* right = new int[n];
	for(int i=0; i<m; i++) {
		left[i] = arr[p+i];
	}
	left[m] = MAX;
	for(int i=0; i<m+1; i++) {
		cout << left[i] << " ";
	}
	cout << endl;
	for(int j=0; j<n; j++) {
		right[j] = arr[q+j];
	}
	right[n] = MAX;
	for(int j=0; j<m; j++) {
		cout << right[j] << " ";
	}

}

int main()
{
	int arr[8] = {2, 4, 5, 7, 1, 2, 3, 6};
	merge(arr, 0, 4, 8);
	return 0;
}
